public class demo1 {
    class Solution {
        int [][]memo;
        public int getMoneyAmount(int n) {
            memo=new int[n+1][n+1];

            return dfs(1,n);
        }
        //遍历以每个数字的开始找出最优解
        public int dfs(int left,int right){
            if(left>=right)return 0;
            if(memo[left][right]!=0){
                return memo[left][right];
            }
            int min=Integer.MAX_VALUE;
            for(int x=left;x<=right;x++){
                int mleft=dfs(left,x-1);
                int mright=dfs(x+1,right);
                min=Math.min(min,Math.max(mleft,mright)+x);//变就变在加x上
            }
            memo[left][right]=min;
            return min;
        }
    }

}
